<
algorithm> (
FIFO, or "queue") A data structure or hardware
buffer from which items are taken out in the same order they
were put in. Also known as a "shelf" from the analogy with
pushing items onto one end of a shelf so that they fall off
the other. A
FIFO is useful for buffering a stream of data
between a sender and receiver which are not synchronised -
i.e. not sending and receiving at exactly the same rate.
Obviously if the rates differ by too much in one direction for
too long then the
FIFO will become either full (
blocking the
sender) or empty (
blocking the receiver). A
Unix pipe
is a common example of a
FIFO.
A
FIFO might be (but isn't ever?) called a LILO - last-in
last-out. The opposite of a
FIFO is a LIFO (last-in
first-out) or "
stack".
(1999-12-06)